{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Game of Nim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #brainteaser #array #math #dynamic-programming #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #脑筋急转弯 #数组 #数学 #动态规划 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nimGame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #Nim 游戏 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 和&nbsp;Bob 交替进行一个游戏，<strong>由 Alice 先手</strong>。</p>\n",
    "\n",
    "<p>在游戏中，共有&nbsp;<code>n</code>&nbsp;堆石头。在每个玩家的回合中，玩家需要 <strong>选择</strong> 任一非空石头堆，从中移除任意 <strong>非零</strong> 数量的石头。如果不能移除任意的石头，就输掉游戏，同时另一人获胜。</p>\n",
    "\n",
    "<p>给定一个整数数组&nbsp;<code>piles</code> ，<code>piles[i]</code> 为 第&nbsp;<code>i</code>&nbsp;堆石头的数量，如果 Alice 能获胜返回&nbsp;<code>true</code><em>&nbsp;</em>，反之返回&nbsp;<code>false</code><em>&nbsp;。</em></p>\n",
    "\n",
    "<p>Alice 和 Bob 都会采取<strong> 最优策略 </strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>piles = [1]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>只有一种可能的情况：\n",
    "- 第一回合，Alice 移除了第 1 堆中 1 块石头。piles = [0]。\n",
    "- 第二回合，Bob 没有任何石头可以移除。Alice 获胜。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>piles = [1,1]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>可以证明，Bob一定能获胜。一种可能的情况：\n",
    "- 第一回合，Alice 移除了第 1 堆中 1 块石头。 piles = [0,1]。\n",
    "- 第二回合，Bob 移除了第 2 堆中 1 块石头。 piles = [0,0]。\n",
    "- 第三回合，Alice 没有任何石头可以移除。Bob 获胜。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>piles = [1,2,3]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>可以证明，Bob一定能获胜。一种可能的情况：\n",
    "- 第一回合，Alice 移除了第 3 堆中 3 块石头。 piles = [1,2,0]。\n",
    "- 第二回合，Bob 移除了第 2 堆中 1 块石头。 piles = [1,1,0]。\n",
    "- 第三回合，Alice 移除了第 1 堆中 1 块石头。piles = [0,1,0]。\n",
    "- 第四回合，Bob 移除了第 2 堆中 1 块石头。 piles = [0,0,0]。\n",
    "- 第三回合，Alice 没有任何石头可以移除。Bob 获胜。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == piles.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 7</code></li>\n",
    "\t<li><code>1 &lt;= piles[i] &lt;= 7</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能想出一个&nbsp;<strong>线性时间&nbsp;</strong>的解决方案吗？虽然这一答案可能超出了面试所需的范围，但了解它可能会很有趣。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [game-of-nim](https://leetcode.cn/problems/game-of-nim/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [game-of-nim](https://leetcode.cn/problems/game-of-nim/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1]', '[1,1]', '[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        k=0\n",
    "        for i in piles:\n",
    "            k^=i\n",
    "        return k!=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def nimGame(self, piles: List[int]) -> bool:\n",
    "#         @cache\n",
    "#         def dfs(p):\n",
    "#             p = list(p)\n",
    "#             for i in range(len(p)):\n",
    "#                 for j in range(1, p[i] + 1):\n",
    "#                     p[i] -= j\n",
    "#                     if not dfs(tuple(p)): return True\n",
    "#                     p[i] += j\n",
    "#             return False\n",
    "\n",
    "#         return dfs(tuple(piles))\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        x = 0\n",
    "        for y in piles: x ^= y\n",
    "        return x > 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        total = piles[0]\n",
    "        for i in range(1, len(piles)) :\n",
    "            total ^= piles[i]\n",
    "        return total != 0 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        ans = 0\n",
    "        for x in piles:\n",
    "            ans ^= x\n",
    "        return bool(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        n=0 \n",
    "        for p in piles:\n",
    "            n^=p      \n",
    "        if n==0:\n",
    "            return False \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        return reduce(xor, piles) != 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        res=0\n",
    "        for i in piles:\n",
    "            res^=i\n",
    "        return res!=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "\n",
    "        SG0 = piles[0]\n",
    "        n = len(piles)\n",
    "        for i in range(1,n):\n",
    "            SG0 ^= piles[i]\n",
    "        return SG0>0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        ans = 0\n",
    "        for i in piles:\n",
    "            ans ^= i \n",
    "        return ans != 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        t = 0\n",
    "        for p in piles:\n",
    "            t ^= p\n",
    "        return t != 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        n=len(piles)\n",
    "        res=0\n",
    "        for i in piles:\n",
    "            res^=i\n",
    "        \n",
    "        if res:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        xor_sum = 0\n",
    "        for pile in piles:\n",
    "            xor_sum ^= pile\n",
    "        \n",
    "        return xor_sum != 0\n",
    "\n",
    "# 测试代码\n",
    "if __name__ == \"__main__\":\n",
    "    sol = Solution()\n",
    "    print(sol.nimGame([3, 4, 5]))  # 输出应该是 True，因为 Alice 可以赢\n",
    "    print(sol.nimGame([3, 3, 3]))  # 输出应该是 False，因为 Alice 会输\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        return functools.reduce(operator.xor, piles) != 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool: \n",
    "        total = piles[0]\n",
    "        for i in range(1 , len(piles)) : \n",
    "            total ^= piles[i]\n",
    "        return total != 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        ans=0\n",
    "        for i in piles:\n",
    "            ans^=i \n",
    "        return ans!=0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "\n",
    "        def g(L):\n",
    "            res = []\n",
    "            for i in L:\n",
    "                if i:\n",
    "                    res.append(i)\n",
    "            return tuple(sorted(res))\n",
    "\n",
    "        @cache\n",
    "        def f(state):\n",
    "            if len(state) == 1:\n",
    "                return True \n",
    "            if len(state) == 2:\n",
    "                if state[0] == state[1]:\n",
    "                    return False \n",
    "                return True\n",
    "            if len(state) == 3:\n",
    "                if state[0] == state[1] or state[1] == state[2]:\n",
    "                    return True \n",
    "            res = True \n",
    "            ln = len(state)\n",
    "            state = list(state)\n",
    "            for i in range(ln):\n",
    "                for j in range(1, state[i] + 1):\n",
    "                    state[i] -= j\n",
    "                    res = res and f(g(state))\n",
    "                    state[i] += j \n",
    "            return not res \n",
    "        \n",
    "        return f(g(piles))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        @cache\n",
    "        def dfs(st):\n",
    "            lst = list(st)\n",
    "            for i, x in enumerate(lst):\n",
    "                for j in range(1, x + 1):\n",
    "                    lst[i] -= j\n",
    "                    if not dfs(tuple(lst)):\n",
    "                        return True\n",
    "                    lst[i] += j\n",
    "            return False\n",
    "\n",
    "        return dfs(tuple(piles))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        @cache\n",
    "        def backtrack(p):\n",
    "            temp=list(p)\n",
    "            for i in range(len(temp)):\n",
    "                for j in range(1,temp[i]+1):\n",
    "                    temp[i]-=j\n",
    "                    if not backtrack(tuple(temp)):\n",
    "                        return True\n",
    "                    temp[i]+=j\n",
    "            return False\n",
    "        return backtrack(tuple(piles))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        n = len(piles)\n",
    "        \n",
    "        @cache\n",
    "        def helper(stones):\n",
    "            stones = list(stones)\n",
    "            \n",
    "            for i in range(n):\n",
    "                if stones[i]:\n",
    "                    for j in range(1, stones[i] + 1):\n",
    "                        stones[i] -= j\n",
    "                        if not helper(tuple(stones)):\n",
    "                            return True\n",
    "                        stones[i] += j\n",
    "        \n",
    "            return False\n",
    "\n",
    "        return helper(tuple(piles))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 记忆化搜索\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(tup):\n",
    "            lst = list(tup)\n",
    "            for i in range(n):\n",
    "                for j in range(1, lst[i] + 1):\n",
    "                    lst[i] -= j\n",
    "                    if not dfs(tuple(lst)):\n",
    "                        return True\n",
    "\n",
    "                    lst[i] += j\n",
    "\n",
    "            return False\n",
    "\n",
    "\n",
    "        n = len(piles)\n",
    "        return dfs(tuple(piles))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        @cache\n",
    "        def dfs(p):\n",
    "            p = list(p)\n",
    "            for i in range(len(p)):\n",
    "                for j in range(1, p[i] + 1):\n",
    "                    p[i] -= j\n",
    "                    if not dfs(tuple(p)): return True\n",
    "                    p[i] += j\n",
    "            return False\n",
    "\n",
    "        return dfs(tuple(piles))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    该解法时间复杂度为7^n*n 由于stones是数组，所以如果要变成记忆化搜索，需要元组化，或者将stones转化\n",
    "    成某个8进制的数字才可以\n",
    "    '''\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        n = len(piles)\n",
    "        \n",
    "        @cache\n",
    "        def helper(stones):\n",
    "            stones = list(stones)\n",
    "            \n",
    "            for i in range(n):\n",
    "                if stones[i]:\n",
    "                    for j in range(1, stones[i] + 1):\n",
    "                        stones[i] -= j\n",
    "                        if not helper(tuple(stones)):\n",
    "                            return True\n",
    "                        stones[i] += j\n",
    "        \n",
    "            return False\n",
    "\n",
    "        return helper(tuple(piles))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(tup):\n",
    "            lst = list(tup)\n",
    "            for i in range(n):\n",
    "                for j in range(1, lst[i] + 1):\n",
    "                    lst[i] -= j\n",
    "                    if not dfs(tuple(lst)):\n",
    "                        return True\n",
    "                    lst[i] += j\n",
    "            return False\n",
    "\n",
    "        n = len(piles)\n",
    "        return dfs(tuple(piles))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "        n=len(piles)\n",
    "        res=0\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(l):\n",
    "            l=list(l)\n",
    "            if l==[0]*n:\n",
    "                return False\n",
    "            \n",
    "            for i in range(n):\n",
    "                for j in range(1,l[i]+1):\n",
    "                    if l[i]-j<0:\n",
    "                        continue\n",
    "                    l[i]=l[i]-j\n",
    "                    \n",
    "                    if dfs(tuple(l))==False:\n",
    "                        return True\n",
    "                    l[i]=l[i]+j\n",
    "            return False\n",
    "\n",
    "        return dfs(tuple(piles))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nimGame(self, piles: List[int]) -> bool:\n",
    "\n",
    "        # 状态压缩,将当前石堆转换为base进制\n",
    "        base = max(piles) + 1\n",
    "\n",
    "        n = len(piles)\n",
    "        init = 0\n",
    "        for i in range(len(piles)):\n",
    "           init = init * base + piles[i]\n",
    "        \n",
    "        # 当前状态先手的胜负状态\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur_state):\n",
    "            if cur_state == 0:\n",
    "                return False\n",
    "            cur_l = []\n",
    "            temp = cur_state\n",
    "            for i in range(n):\n",
    "                cur_l.insert(0,temp % base)\n",
    "                temp //= base\n",
    "    \n",
    "            for i in range(n):\n",
    "                if cur_l[i] > 0:\n",
    "                    for j in range(1,cur_l[i] + 1):\n",
    "                        next_state = cur_state - j * pow(base,n - 1 - i)\n",
    "                        if not dfs(next_state):\n",
    "                            return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(init)   \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
